package suanfa;

import java.util.*;

class Solution {
    public static void merge() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        Integer[] integers = new Integer[3];
        list.toArray(integers);
        System.out.println(Arrays.toString(integers));

    }


    public static int removeElement(int[] nums, int val) {
        int count = 0;
        List<Integer> list = new ArrayList();
        for (int index : nums) {
            if (index != val) {
                count++;
                list.add(index);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (i < count) {
                nums[i] = list.get(i);
            } else {
                nums[i] = 0;
            }

        }


        return count;


    }

    public static int removeDuplicates(int[] nums) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int index : nums) {
            map.put(index, index);
        }
        Set<Integer> keys = map.keySet();
        int length = map.size();
        int i = 0;
        for (int key : keys) {
            nums[i] = key;
            i++;
        }
        System.out.println(Arrays.toString(nums));

        return length;
    }

    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int majorityElement = nums[0];
        for (int index : nums) {

            map.put(index, map.getOrDefault(index, 0) + 1);
            if (map.get(index) > nums.length / 2) {
                majorityElement = index;
                break;
            }
            return majorityElement;


        }
        return majorityElement;

    }

    public static void rotate(int[] nums, int k) {

        int length = nums.length;

        if (k > length) {
            k = k % length;
        } else if (k == length) {
            return;
        }

        int[] numsNew = new int[length];
        int mid = length - k;
        for (int index = 0; index < k; index++) {
            numsNew[k - index - 1] = nums[length - index - 1];

        }

        for (int index = 0; index < length - k; index++) {
            numsNew[k + index] = nums[index];
        }
        int i = 0;
        for (int index : numsNew) {
            nums[i] = numsNew[i];
            i++;
        }
        System.out.println(Arrays.toString(nums));
    }

    public static int maxProfit(int[] prices) {
        int length = prices.length;
        int max = 0;
        if (length <= 1) {
            return 0;
        } else if (length == 2) {
            return prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0;
        }

        for (int j = 0; j < length - 1; j++) {
            int currentPrice = prices[j];
            int finalPrice = prices[length - 1];
            int finalChange = finalPrice - currentPrice;
            int currentMax = 0;
            for (int i = j + 1; i < length - 1; i++) {
                if (prices[i] > currentPrice && prices[i + 1] < prices[i]) {
                    int maxValue = prices[i] - currentPrice;
                    currentMax = maxValue > currentMax ? maxValue : currentMax;
                }
            }

            if (currentMax > 0) {
                currentMax = currentMax > finalChange ? currentMax : finalChange;
            } else {

                currentMax = finalChange > 0 ? finalChange : 0;
            }


            if (currentMax > max) {
                max = currentMax;
            }


        }
        return max;

    }

    public static int maxProfit2(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxProfit = 0;


        for (int i = prices.length - 1; i > 0; i--) {

            for (int j = i - 1; j >= 0; j--) {
                int profit = prices[i] - prices[j];
                maxProfit = profit > maxProfit ? profit : maxProfit;
            }


        }
        return maxProfit;


    }

    public static int maxProfit3(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxProfit = 0;


        for (int i = 0; i < prices.length - 1; i++) {

            if (prices[i + 1] > prices[i]) {
                maxProfit += prices[i + 1] - prices[i];
            }


        }
        return maxProfit;


    }

    public static boolean canJump(int[] nums) {


        boolean flag = true;
        boolean firstZero = true;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i + nums[i] >= nums.length) {
                return true;
            }

            if (nums[i] == 0 && !firstZero) {
                flag = false;
                for (int j = i - 1; j > index; j--) {
                    if (nums[j] > i - j) {
                        flag = true;
                        break;
                    }


                }
                if (!flag)
                    return false;
                index = i;
            }

            if (nums[i] == 0 && firstZero) {
                flag = false;
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[j] > i - j) {
                        flag = true;
                        firstZero = false;
                        break;
                    }


                }

                index = i;
                if (!flag) {
                    return false;
                }


            }


        }
        return flag;


    }

    public static boolean canJump2(int[] nums) {
        int length = nums.length;
        int maxCanArrive = 0;
        for (int i = 0; i < length - 1; i++) {
            if (i <= maxCanArrive) {
                maxCanArrive = Math.max(maxCanArrive, i + nums[i]);
                if (i + maxCanArrive >= length - 1) {
                    return true;
                }
            }


        }
        return false;


    }

    public static int hIndex(int[] citations) {


        if (citations.length == 0) {
            return 0;
        }
        if (citations.length == 1) {
            return citations[0] >= 1 ? 1 : 0;
        }

        int count = 0;
        for (int index : citations) {
            count += index;
        }
        if (count == 0) {
            return 0;
        }

        int length = citations.length;
        Arrays.sort(citations);
        int midIndex = length / 2;
        int h = 0;
        int midVal = citations[midIndex];
        if (midIndex <= midVal) {
            while (citations[length - midIndex] >= midIndex) {
                if (midIndex == length)
                    break;

                midIndex++;
            }

            h = citations[length - midIndex] >= midIndex ? midIndex : midIndex - 1;

        } else {

            if (midVal == 0) {
                int[] a = new int[length - midIndex - 1];
                int i = 0;
                int index = midIndex + 1;
                while (index < citations.length) {
                    a[i] = citations[index];
                    i++;
                    index++;
                }
                h = hIndex(a);
                return h;


            }


            while (citations[length - midVal] >= midVal) {
                if (midVal == length)
                    break;
                midVal++;
            }
            h = citations[length - midVal] >= midVal ? midVal : midVal - 1;

        }
        return h;

    }


    public static void main(String[] args) {
        int[] num1 = {1, 2, 0, 1, 2, 1, 0, 4, 2};
        int[] nums2 = {1, 3, 3, 3, 3, 2, 2, 3, 3, 1};
        int[] nums3 = {7, 1, 5, 3, 6, 4};
        int[] nums4 = {7, 6, 4, 4, 1};
        int[] nums5 = {0, 1, 0};
        int[] nums6 = {3, 0, 6, 1, 5};

//        int[] num2 = {2, 5, 6};
//        int[] merge = merge(num1, num1.length, num2, num2.length);
//        System.out.println(Arrays.toString(merge));

//        merge();
//        System.out.println(removeElement(num1, 2));
//        System.out.println(removeDuplicates(nums2));

//        System.out.println(majorityElement(nums2));

//        rotate(num1, 3);

        System.out.println(hIndex(nums5));

    }
}